package sort;

import java.util.Arrays;
import java.util.Scanner;
/**
 * @ClassName: merge
 * @Auther: Drawin
 * @Date: 2021/9/20 22:31
 * @Description:
 */

public class merge {
    public static void main(String[] args) {
        System.out.println("请输入数组个数：");
        Scanner s=new Scanner(System.in);
        int n=s.nextInt();
        int[] a= new int[n];
        for(int i=0;i<a.length;i++){
            a[i]=s.nextInt();
        }
        int [] b=new int[a.length];
        mergesort(a,0,a.length-1,b);
        System.out.println(Arrays.toString(a));
    }

    public static void merge(int []a,int low,int mid,int high,int[]b) {
        int i=0;
        int j=low,k=mid+1;
        while (j<=mid&&k<=high){
            if(a[j]<a[k]){
                b[i++]=a[j++];
            }else{
                b[i++]=a[k++];
            }
        }
        while(j<=mid){
            b[i++]=a[j++];
        }
        while(k<=high){
            b[i++]=a[k++];
        }
        for(int t=0;t<i;t++){
            a[low+t]=b[t];
        }
    }
    public static void mergesort(int[]a,int low,int high,int[]b){
        if(low<high){
            int mid=(low+high)/2;
            mergesort(a,low,mid,b);
            mergesort(a,mid+1,high,b);
            merge(a,low,mid,high,b);
        }
    }
}
